\chapter{符号表}

    编译的各个阶段都要大量使用符号表. 本章研究如何合理组织符号表, 方便使用.

    \section{符号表的内容}

        \subsection{符号表要实现的功能} 
        
            查找判断存在性, 查找获取信息, 填入, 更新, 删除.

        \subsection{基本形态} 
        
            变量名, 变量信息(通常有多个域). 采用分表的方式方便随机访问和节约空间, 很多栏目对于很多符号是无意义的.

            \subsubsection{变量名域的处理}

                如果变量名的长度可变, 通常将变量名实际存放在堆里, 只在符号表里放置对符号名的引用.

    \section{符号表的原理和实现}

        \subsection{原理}

            \subsubsection{建立时机} 
            
                词法分析识别了标识符时, 语法分析器分析出种类等信息时.

            \subsubsection{插入时机}

                显式说明时插入能获得的属性; 从语法中可以获得隐含的属性(如标号). 

            \subsubsection{组织方案} 
            
                线性表, 折半查找, 哈希表. 此外还要解决冲突问题, 因此需要引入探查机制: (内部解决) 线性探查法(开放探查法), 二次探查法, 平方探查法, (外部解决) 链表法, \ldots

        \subsection{实现}

            \begin{description}
                \item[自适应表] 维护最近访问状态信息, 考虑了局部性原理, 有一定的额外开销. 静态空间, 动态顺序的链表, 不适合随机访问.
                \item[二分表] 有序表, 可以估计探查. 一旦修改就要重新整理, 不适合名字表等频繁修改的表.
                \item[有序二叉树] 空间开销大.
                \item[Trie-树] 空间和时间开销可能也挺大的.
                \item[哈希表] 难以预先确定空间大小, 需要考虑溢出问题. 总时间$=$计算时间$+$查找长度. 因此需要尽量减小查找长度.
            \end{description}

    \section{符号的作用域}

        在不冲突的情况下, 不同的符号可以在不同的段落中拥有相同的名字. 符号表应当处理好这个问题.

        \subsection{Fortran语言的两层作用域}

            Fortran语言采用模块结构, 存在局部和全局作用域层次, 分块编译时采用双向对开线性表实现: 用两个指针分别指向局部表和全局表的顶端, 处理完一段之后重置局部名表指针. 若采用了多遍编译, 就需要把符号表保存到外部供后续过程取用.

        \subsection{ALGOL语言的最近嵌套原则}

            ALGOL语言中使用了\textsf{最近嵌套原则}: 遇到标识符的时候需要从最内层的子程序中调用这个符号. 每个过程对应一个编号, 按照过程编号来引用符号.

            \subsubsection{分层变量符号表} 
            
                哈希链分为活名区和死名区, 死名区的数据不能立即丢弃, 因为从子程序退出之后需要取出死名区的信息. 哈希链上的元素指向变量信息四元组(变量名, 生存期, 同名next域). 5个表通过指针相联系:
                \begin{description}
                    \item[哈希表 HT] 哈希表指向符号表, 为了解决因此产生的哈希碰撞(通常是因为重名)需要构造符号表上的哈希链. 
                        注意: 哈希链保证了倒序查找!
                    \item[变量名串 Char String] 表现为栈.
                    \item[符号信息表 INFO] 符号表里的信息部分.
                    \item[符号表 Symbol Table] 表现为栈.
                    \item[块表 Block Table] 块表指向符号表和变量名串中对应块
                \end{description}
                
                常规动作: 填新项, 进入子程序, 查表, 退出子程序(切断哈希链).
